package sit.engreal.leetcode.problems600;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * <a href="https://leetcode.cn/problems/01-matrix/">542. 01 矩阵</a>
 */
public class LeetCode542 {
    public int[][] updateMatrix(int[][] mat) {
        final int m = mat.length;
        final int n = mat[0].length;

        final int[][] fork = new int[m][];
        for (int i = 0; i < m; i++) {
            fork[i] = new int[n];
            for (int j = 0; j < n; j++) {
                fork[i][j] = Integer.MAX_VALUE;
            }
        }

        final ArrayDeque<int[]> deque = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    deque.add(new int[]{i, j});
                }
            }
        }
        int distance = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                final int[] p = deque.removeFirst();
                final int i = p[0];
                final int j = p[1];
                if (distance > fork[i][j]) {
                    continue;
                }
                fork[i][j] = distance;
                if (i - 1 >= 0 && fork[i - 1][j] == Integer.MAX_VALUE) {
                    deque.addLast(new int[]{i - 1, j});
                }
                if (i + 1 < m && fork[i + 1][j] == Integer.MAX_VALUE) {
                    deque.addLast(new int[]{i + 1, j});
                }
                if (j - 1 >= 0 && fork[i][j - 1] == Integer.MAX_VALUE) {
                    deque.addLast(new int[]{i, j - 1});
                }
                if (j + 1 < n && fork[i][j + 1] == Integer.MAX_VALUE) {
                    deque.addLast(new int[]{i, j + 1});
                }
            }
            distance++;
        }

        return fork;
    }

    public static void main(String[] args) {
        final int[][] mat = {
                {0, 0, 0},
                {0, 1, 0},
                {1, 1, 1,}
        };
        final LeetCode542 demo = new LeetCode542();
        final int[][] distance = demo.updateMatrix(mat);
        final String text = Arrays.stream(distance).map(Arrays::toString).collect(Collectors.joining("\n"));
        System.out.println(text);
    }
}
